/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2022-10-05
 * Time: 14:55
 */
public class TestBinaryTree {
    static class TreeNode{
          char val;
          TreeNode left;
          TreeNode right;
          TreeNode(char val){
              this.val = val;
          }
    }
    //先序遍历创建二叉树
    private int i = 0;
    public TreeNode createTree(String str){
        TreeNode root = null;
        if(str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }

    // 获取树中节点的个数
    int size(TreeNode root){
        if(root == null){
            return 0;
        }
        return size(root.left)+size(root.right) + 1;
    }
    // 获取叶子节点的个数
    int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

// 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root,int k){
        if(root == null || k <= 0){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }
    //先序遍历
    void preorder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val+" ");
        preorder(root.left);
        preorder(root.right);
    }
    //中序遍历
    void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
    //后序遍历
    void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    //获取二叉树的高度
//    public int getHeight(TreeNode root){
//        if(root == null){
//            return 0;
//        }
//        int leftHeight = getHeight(root.left);
//        int rightHeight = getHeight(root.right);
//        return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
//
//    }
       public int getHeight(TreeNode root){
            if(root == null){
                return 0;
            }
            return getHeight(root.left) > getHeight(root.right) ? getHeight(root.left)+1
                    : getHeight(root.right)+1;
       }
       public TreeNode find(TreeNode root,char val){
            if(root == null){
                return null;
            }
            if(root.val == val){
                return root;
            }
            TreeNode ret1 = find(root.left,val);
             if(ret1 != null){
                 return ret1;
             }
             TreeNode ret2 = find(root.right,val);
             if(ret2 != null){
                 return ret2;
             }
             return null;
       }
       public TreeNode invertTree(TreeNode root){
            if(root == null){
                return null;
            }
            TreeNode tmp = root.left;
            root.left = root.right;
            root.right = tmp;
            invertTree(root.left);
            invertTree(root.right);
            return root;

       }
}
